package com.tju.ffmpeg

import org.junit.Test

/**
 * vector<vector<unsigned>> matrix{
{0,  20, 30, 10, 11},
{20, 0,  16, 4,  2},
{30, 16, 0,  6,  7},
{10, 4,  6,  0,  12},
{11, 2,  7,  12, 0},
};

 */

class TencentSecond {
    @Test
    fun test() {
        val matrix: Array<IntArray> = arrayOf(
                intArrayOf(0, 20, 30, 10, 11),
                intArrayOf(20, 0,  16, 4,  2),
                intArrayOf(30, 16, 0,  6,  7),
                intArrayOf(10, 4,  6,  0,  12),
                intArrayOf(11, 2,  7,  12, 0)
        )
        val res = solute(matrix)
        println(res.sum)
        res.array.forEach {
            print("$it ")
        }
    }

    fun solute(matrix: Array<IntArray>): MatrixResult {
        if (matrix.isEmpty()) {
            return MatrixResult(0)
        }
        val nums = matrix.size
        val result = MatrixResult(nums)
        result.sum = Int.MAX_VALUE
        val visited: BooleanArray = BooleanArray(nums){ false }
        dfs(matrix, mutableListOf<Int>(), visited, result, 0)
        return result
    }

    fun dfs(matrix: Array<IntArray>, trace: MutableList<Int>, visited: BooleanArray, result: MatrixResult, curSum: Int) {
        var cur = curSum
        if (trace.size == matrix.size) {
            val col = trace[trace.size-1]
            val row = trace[0]
            val distance = matrix[col][row]
            cur += distance
            if (cur<result.sum) {
                result.sum = cur
                result.array = trace.toIntArray()
            }
            return
        }
        for(i in matrix.indices) {
            if (visited[i]) continue
            var pre = i
            if(trace.size>0) {
                pre = trace[trace.size-1]
            }
            visited[i] = true
            trace.add(i)
            cur += matrix[pre][i]
            dfs(matrix, trace, visited, result, cur)
            cur = curSum
            trace.removeAt(trace.size-1)
            visited[i] = false
        }
    }

    class MatrixResult(val nums: Int) {
        var array: IntArray = IntArray(nums) {0}

        var sum: Int = 0
    }
}

